#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

typedef struct Node
{
	int val;
	struct Node* next;
	struct Node* random;

}Node;
struct Node* copyRandomList(struct Node* head)
{
	if (head == NULL)
		return NULL;
	struct Node* cur = head;
	struct Node* next = cur->next;

	//在每一个原节点后面赋值链接
	while (cur)
	{
		struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
		//赋值
		newnode->val = cur->val;
		//链接
		newnode->next = next;
		cur->next = newnode;
		//cur和next向后移动
		cur = next;
		if (next != NULL)
			next = next->next;
	}
	//恢复cur和copy的初始位置
	cur = head;
	struct Node* copy = cur->next;
	//置random
	while (cur)
	{
		if (cur->random == NULL)
		{
			copy->random = NULL;
		}
		else
		{
			copy->random = cur->random->next;
		}

		cur = copy->next;
		if (cur != NULL)
			copy = cur->next;

	}

	//将所有的newnode节点取下来尾插
	//新的链表的头结点和尾节点
	struct Node* tail = NULL;
	struct Node* newhead = NULL;
	//恢复cur和copy和next的位置
	cur = head;
	copy = cur->next;
	next = copy->next;
	while (cur)
	{
		if (tail == NULL)
		{
			tail = newhead = copy;
		}
		else
		{
			tail->next = copy;
			tail = tail->next;
		}
		cur = next;
		if (next != NULL)
		{
			copy = next->next;
			next = copy->next;
		}
	}
	//返回新链表的头结点
	return newhead;
}
int main()
{
	Node* node1 = (Node*)malloc(sizeof(Node));
	node1->val = 7;

	Node* node2 = (Node*)malloc(sizeof(Node));
	node2->val = 13;

	Node* node3 = (Node*)malloc(sizeof(Node));
	node3->val = 11;

	Node* node4 = (Node*)malloc(sizeof(Node));
	node4->val = 10;

	Node* node5 = (Node*)malloc(sizeof(Node));
	node5->val = 1;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = node5;
	node5->next = NULL;

	node1->random = NULL;
	node2->random = node1;
	node3->random = node5;
	node4->random = node3;
	node5->random = node1;


	Node* newhead = copyRandomList(node1);
	return 0;
}
